// 1. 首先想到暴力解 遍历所有可能的a 与 b 数组的起始位置 然后寻找最长公共前缀 时间复杂度为 立方
// 2. 尝试降低时间复杂度 其题目为求解最优化问题 则想到贪心 和动态规划 此题用动态规划思想非常容易得出递推式 时间复杂度 为平方
// 3. 在尝试降低复杂度 为n long n左右 因此想到了 二分方法 又因为是两个数组 所以想到将其中一个 进行哈希处理 具体方法不展开了
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int M = A.size();
        int N = B.size();
        // dp[i][j] means the longest common subarray ending with A[i], B[j]
        // note: must end with A[i], B[j], including them!
        vector<vector<int>> dp(M + 1, vector<int>(N + 1, 0));
        int res = 0;
        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N; j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = 0;
                }
                res = max(res, dp[i][j]);
            }
        }    

        return res;
    }
};